# https://leetcode.cn/problems/sum-of-distances-in-tree/description/

class Solution:
    @staticmethod
    def sumOfDistancesInTree(n: int, edges: list[list[int]]) -> list[int]:
        # 建立邻接表
        adjacencyList = [[] for _ in range(n)]
        for i, j in edges:
            adjacencyList[i].append(j)
            adjacencyList[j].append(i)
        # 节点链接其所有孩子节点的总边数（初始以节点0为根节点）
        nodeEdgeCount = [0 for _ in range(n)]

        # 初始化
        def initialization(root: int, father: int, level: int) -> int:
            res: int = 0
            for nextNode in adjacencyList[root]:
                if nextNode == father:
                    continue
                res += initialization(nextNode, root, level + 1)
                nodeEdgeCount[root] += nodeEdgeCount[nextNode]
            nodeEdgeCount[root] += len(adjacencyList[root]) - 1 if father >= 0 else len(adjacencyList[root])
            return res + level * (len(adjacencyList[root]) - 1) if father >= 0 else res + level * (len(adjacencyList[root]))

        ans = [0 for _ in range(n)]
        ans[0] = initialization(0, -1, 1)
        print(nodeEdgeCount)

        # 动态规划
        def dp(root: int, father: int) -> None:
            # 状态转移
            if father != -1:
                nodeEdgeCount[father] -= nodeEdgeCount[root] + 1
                ans[root] = ans[father] + nodeEdgeCount[father] - nodeEdgeCount[root]
                nodeEdgeCount[root] += nodeEdgeCount[father] + 1
            # 下一个节点
            for nextNode in adjacencyList[root]:
                if nextNode == father:
                    continue
                dp(nextNode, root)
            # 回溯
            if father != -1:
                nodeEdgeCount[root] -= nodeEdgeCount[father] + 1
                nodeEdgeCount[father] += nodeEdgeCount[root] + 1

        dp(0, -1)
        return ans
